

/** Implementation of the Dynamic Disjoint Sets ADT.
 * 
 * Elements are integers in the range [1, numElements],
 * where numElements is the argument passed to the object's
 * constructor.
 *
 * 
 * Not sure why elements can't be integers in [0, numElements - 1],
 * given that we're using signed integer indices, and that the sample code
 * seems to have been written with a zero-indexed array in mind.*/
public class UnionFind {
	
	/** Initializes a UnionFind object with numElements singleton sets
	 * 
	 * @param numElements The total number of elements contained by
	 * the new object's sets.
	 * 
	 * @throws IllegalArgumentException if numElements < 2 
	 */
	public UnionFind(int numElements) {
		// Validate input
		if (numElements < 2)
			throw new IllegalArgumentException("Cannot construct Unionfind" +
					" with fewer than two elements.");
		
		numSets = numElements;
		++numElements;
		parents = new int[numElements];
		weights = new int[numElements];
				
		for (int i = 1; i < numElements; ++i) {
			parents[i] = -1;
			weights[i] = 1;
		}
	}
	
	/** Given two set representatives, performs weighted union on their sets.
	 *
	 * @param i The representative of a set.
	 * @param j The representative of a set.
	 * 
	 * @throws IllegalArgumentException if either element is not
	 * a representative of its set. 
	 */
	public void union(int i, int j) {
		// Validate input
		if (find(i) != i || find(j) != j)
			throw new IllegalArgumentException("Set union:" +
					" argument is not a representative of its set");
		
		// Are i and j the same set?
		if (i == j)
			return;
		
		// Nope. Attache lighter to heavier, sum weights, decrement set count
		int totalWeight = weights[i] + weights[j];
		
		if (weights[i] < weights[j]) {
			parents[i] = j;
			weights[j] = totalWeight;
		}
		else {
			parents[j] = i;
			weights[i] = totalWeight;
		}
		
		--numSets;
	}
	
	/** Returns the representative of a given element's set.
	 * 
	 * Also optimizes future find() calls via path compression.
	 * 
	 * @param i The element whose set representative should be returned.
	 *  
	 * @return the representative of the set containing element i.
	 * 
	 * @throws IllegalArgumentException if argument is zero or out of bounds.
	 */
	public int find(int i) {
		// Validate input. Somewhat needlessly.
		if (i < 1 || i >= parents.length)
			throw new IllegalArgumentException("Element outside range");
		
		// Is the element a representative?
		int parent = parents[i];
		
		if (parent == -1)
			return i;
		
		// No. Find representative. Recursively make it each ancestor's parent
		parent = find(parent);
		
		// Make it this element's parent and return it
		parents[i] = parent;
		
		return parent;
	}
	
	/** Returns the number of disjoint sets in the object.
	 * 
	 * @return the number of disjoint sets in the object.
	 */
	public int getNumSets() {
		return numSets;
	}
	
	/** Returns an array containing the representatives of
	 * every set, in ascending order.
	 * 
	 * Runtime proportional to the total number of
	 * elements in the object.
	 * 
	 * @return an array of set representatives.
	 */
	public int[] getRepresentatives() {
		int[] result = new int[numSets];
		
		int currentRepresentative = 0;
		
		for (int i = 1; i < parents.length; ++i)
			if (parents[i] == -1) {
				result[currentRepresentative] = i;
				
				++currentRepresentative;
			}
		
		return result;		
	}
	
	/** Tracks the parents of set elements.
	 * 
	 * parents[i] is the parent of element i.
	 * 
	 * parents[i] == -1 indicates that i is the root of its up-tree.*/
	private int[] parents;
	
	/** Tracks the weights of sets via their representatives. 
	 * 
	 * weights[i] is the weight of the set represented by i.
	 * 
	 * Only valid for set representatives. If i is a non-representative
	 * element of a set, weights[i] will be smaller than the actual weight
	 * of its set.*/
	private int[] weights;
	
	private int numSets;

}
